# 环境治理(好题, Floyd 弗洛伊德 最短路径 路径之和)
"""题目:
共有n个城市, 从LQ 国拥有 n 个城市，从 0到 n − 1 编号，这 n 个城市两两之间都有且仅有一条双向道路连接，这意味着任意两个城市之间都是可达的。
每条道路都有一个属性 D ，表示这条道路的灰尘度。当从一个城市 A 前往另一个城市 B 时，可能存在多条路线，每条路线的灰尘度定义为这条路线所经过的
所有道路的灰尘度之和，LQ 国的人都很讨厌灰尘，所以他们总会优先选择灰尘度最小的路线。
LQ 国很看重居民的出行环境，他们用一个指标 P 来衡量 LQ 国的出行环境，P 定义为：
 sum(sum(d(i, j)))
其中 d ( i , j ) 表示城市 i 到城市 j 之间灰尘度最小的路线对应的灰尘度的值。
为了改善出行环境，每个城市都要有所作为，当某个城市进行道路改善时，会将与这个城市直接相连的所有道路的灰尘度都减少 1 ，但每条道路都有一个灰尘度
的下限值 L ，当灰尘度达到道路的下限值时，无论再怎么改善，道路的灰尘度也不会再减小了。
具体的计划是这样的：
第 1 天, 对 0 号城市相连接的道路环境进行改善
第 2 天, 对 1 号城市相连接的道路环境进行改善
......
第 n 天, 对 n - 1 号城市相连接的道路环境进行改善
第 n + 1 天, 对 0 号城市相连接的道路环境进行改善
......

LQ 国想要使得 P 指标满足 P ≤ Q。请问最少要经过多少天之后，P 指标可以满足 P ≤ Q 。如果在初始时就已经满足条件，则输出 0 ；
如果永远不可能满足，则输出 − 1 。
"""
from leetcode import test_function


def find_day(D, L, Q):
    """FLoyd算法"""
    n = len(D)

    def floyd(temp):
        """floyd求temp临时矩阵的P值"""
        nonlocal L

        for i in range(n):  # 起始节点
            for j in range(n):  # 目的节点
                for k in range(n):  # 中转节点
                    if temp[i][j] > temp[i][k] + temp[k][j]:
                        temp[i][j] = temp[i][k] + temp[k][j]
        return sum(sum(temp[i]) for i in range(n))

    def clean(x: int):
        remain = x % n
        cycle = x // n
        temp = [[D[i][j] for j in range(n)] for i in range(n)]  # temp表示经过t天之后的图的临界矩阵
        for i in range(n):
            for j in range(n):
                if i < remain:
                    temp[i][j] -= 1
                    temp[j][i] -= 1
                temp[i][j] = max(L[i][j], temp[i][j] - cycle)
                temp[j][i] = max(L[j][i], temp[j][i] - cycle)
        return temp

    day = 0
    p = float("inf")
    while p > Q:
        t = clean(day)
        p = floyd(t)
        day += 1

    return day - 1


def find_day_opt(D, L, Q):
    """Floyd算法 + 二分法"""
    left = 0
    right = int(1e7)
    ans = -1
    n = len(D)  # 节点数量

    while left <= right:
        mid = (left + right) // 2
        total = mid  # total表示经历的天数
        remain = total % n  # 表示在最后一个不完整周期中，有 remain 天（从节点 0 到节点 remain-1 获得了额外更新）。
        cycle = total // n  # 经历了多少个完整周期（周期为 n 天，每天依次更新一个节点）。

        fmp = [[D[i][j] for j in range(n)] for i in range(n)]  # fmp表示经过t天之后的图的临界矩阵
        for i in range(n):
            for j in range(n):
                if i < remain:
                    fmp[i][j] -= 1
                    fmp[j][i] -= 1
                fmp[i][j] = max(L[i][j], fmp[i][j] - cycle)
                fmp[j][i] = max(L[j][i], fmp[j][i] - cycle)

        # Floyd算法的核心部分
        # k为中间点
        for k in range(n):
            # i为起点
            for i in range(n):
                # j为终点
                for j in range(n):
                    if fmp[i][j] > fmp[i][k] + fmp[k][j]:
                        fmp[i][j] = fmp[i][k] + fmp[k][j]  # 更新最小路径
        s = sum([sum(fmp[i]) for i in range(n)])

        if s <= Q:
            right = mid - 1
            ans = mid
        else:
            left = mid + 1

    return ans


if __name__ == '__main__':
    # n, Q = map(int, input().split())
    # D, L = [], []
    # for _ in range(n):
    #     D.append(list(map(int, input().split())))
    #
    # for _ in range(n):
    #     L.append(list(map(int, input().split())))
    with open("../../data/2022_underb_g.in", "r") as file:
        n, Q = map(int, file.readline().split())
        D, L = [], []
        for _ in range(n):
            D.append(list(map(int, file.readline().split())))

        for _ in range(n):
            L.append(list(map(int, file.readline().split())))

    inp = [{"D": [[0, 2, 4], [2, 0, 1], [4, 1, 0]], "L": [[0, 2, 2], [2, 0, 0], [2, 0, 0]], "Q": 10},
           {"D": D, "L": L, "Q": Q}, ]
    out = [2, 31]
    test_function(find_day, inp, out)
    test_function(find_day_opt, inp, out)
